package 动态规划.另类的;
/*
 * 这道题 主要 是 二 和 三 这种特殊情况  拆了  乘积 反而更小一些
 * 主要是 这道题的  dp 的 想法 好像有点特殊, 复习的时候注意些!
 *
 *
 */
public class leetcode343整数拆分 {
	static int a;
	public static void main(String []args) {
		System.out.println(process(12));
		System.out.println(a);
	}
	//  二愣子 才明白 过来  ？？？  递归 不就是 一种 循环嘛 递归 本身 就是 一个 循环 啊
	public static int dp(int n) {
		if(n==1) {
			return 1;
		}
		if(n==2) {
			return 1;
		}
		if(n==3) {
			return 2;
		}
		// n > 3
		int dp[] = new int [n+1];
		dp[1]=1;
		dp[2]=2;
		dp[3]=3;
		for(int rest=4; rest<= n; rest++) {
			int ans=1;
			for(int i=2; i<=rest/2;i++) {
				//   这里 dp[i] 和  i 一样的效果 但 是 具体 情况 不一样 
	// 如果 写  i的 话  i< (=) rest  这样 符合 暴力递归
				//ans= Math.max(ans,dp[rest-i]*i);
				ans= Math.max(ans,dp[rest-i]*dp[i]);
			}
			dp[rest]=ans;
		}
		return dp[n];
	}
	public static int process(int rest) {
		a++;
		if(rest == 1 ) {
			return 1;
		}
		if(rest==2) {
			return 2;
		}
		if(rest==3) {
			return 3;
		}
		int ans=1;
		for(int i=2;i <= rest/2;i++ ) {
		//	ans= Math.max(ans,process(rest-i)*i);   i< rest 这种组合  157 次递归
			ans= Math.max(ans,process(rest-i)*process(i));
			// 这种组合  123 次递归
		}
		return ans;
//		for(int i=rest; i>= 2 ; i--) {
//			ans
//		}
	}
	//这上面 和 下面  两种 dp的方式 差不多 也算是coding 上的 问题 
	public static int process1(int rest) {
		// 这个 basecase  不写 也行 但走的 路 稍微 稍微长了 那么 一点点
		if(rest == 1 ) {
			return 1;
		}
		if(rest==2) {
			return 1;
		}
//		if(rest==3) {
//			return 3;
//		}
		int ans=1;
		for(int i=2;i <= rest;i++ ) {
			ans= Math.max(ans,Math.max((rest-i)*i, process1(rest-i)*i));
		}
		return ans;
//		for(int i=rest; i>= 2 ; i--) {
//			ans
//		}
	}


	/*
	 试试这种新的思想 ， 行不行
	 就 2 和 3 有点特殊， 这个 题，还挺 搞得说实话！

	 这个 题 重点 标注一下，    剪绳子II！
	 */
	public int integerBreak(int n) {
		// return solution(n)
		// return dp(n);
		if(n == 2 || n == 3){
			return n - 1;
		}
		return recursion(n);
	}
	public int recursion(int rest){
		if(rest == 0){
			return 1;
		}
		int ans = 1;
		for(int i = 1; rest - i >= 0;i++){
			ans = Math.max(ans,recursion(rest - i) * i);
		}
		return ans;
	}


	public int dpOne(int n){
		if(n == 2 || n == 3){
			return n - 1;
		}
		int dp[] = new int[n + 1];
		dp[0] = 1;
		for(int i = 4;i <= n;i++){
			int ans = 1;
			for(int j = 1;i - j >=0 ;j++){
				ans = Math.max(ans,dp[i - j] * j);
			}
			dp[i] = ans;
		}
		return dp[n];
	}
}
